#include<bits/stdc++.h>

using namespace std;

const int N=15005;
struct lqq{
	int l,r,sum;
}tr[N*4];
void build()
